package greedy_algorithm;

import java.util.*;

/**
 * 子序列最大优雅度 -2813
 */
public class 子序列最大优雅度 {
    public static void main(String[] args) {
        int[][] items = {{3, 1}, {3, 1}, {2, 2}, {5, 3}};
//        int[][] items = {{4, 1}, {1, 1}};
        System.out.println(new 子序列最大优雅度().findMaximumElegance(items, 3));
    }

    public long findMaximumElegance(int[][] items, int k) {
        // 将物品按利润从高到低排序
        Arrays.sort(items, (a, b) -> b[0] - a[0]);

        long ans = 0; // 存储最大优雅度的变量
        long totalProfit = 0; // 存储总利润的变量
        Set<Integer> categories = new HashSet<>(); // 用于存储不同类别的集合
        Deque<Integer> deque = new ArrayDeque<>(); // 用于存储重复类别的利润

        for (int i = 0; i < items.length; i++) {
            int profit = items[i][0]; // 获取当前物品的利润
            int category = items[i][1]; // 获取当前物品的类别

            // 处理前 k 个物品
            if (i < k) {
                totalProfit += profit; // 累加利润
                if (!categories.add(category)) {
                    deque.push(profit); // 如果类别重复，将利润存入 deque
                }
            }
            // 处理第 k+1 个及之后的物品
            else if (!deque.isEmpty() && categories.add(category)) {
                totalProfit += profit - deque.pop(); // 如果新类别未曾添加过，则用新的类别项目替换掉一个重复类别项目的最小利润
            }
            ans = Math.max(ans, totalProfit + (long) categories.size() * categories.size()); // 更新最大优雅度
        }
        return ans;
    }

}
